The technical field of this invention is overflow detection for shifter circuits used in data processing.
Detection of overflow when shifting data in an arithmetic logic unit (ALU) requires logic with significant propagation delay. Often overflow detection takes more time than the shift operation that generates the overflow. The conventional algorithm for overflow detection performs mask generation and data propagation serially or sequentially. This algorithm may be described as follows. First a shift mask is generated from the binary value of the desired impending shift.
Table 1 shows an example of the shift mask generation for 16-bit shifter. The mask has five leading bits xe2x80x981xe2x80x99, ten following bits xe2x80x980xe2x80x99 and a least significant bit that is a don""t care (X).
In the next step the mask is used to filter the data with AND gates as follows. The least significant bit of the data is ignored because it will never be shifted out by shift operation. Table 2 shows 16-bit filtering for the example shift value of 5 (binary 0101).
The resulting bit sequence contains xe2x80x981xe2x80x99 bits if the shift would cause an overflow. The propagation circuit detects occurrence of xe2x80x981xe2x80x99 bits by taking a logical OR of each bit in the sequence, and xe2x80x981xe2x80x99 appears at the overflow output OVF when overflow occurs.
This conventional algorithm takes significant time tc execute because data propagation for the OR operation starts ration and masking operation complete. The truth table for 16-Bit overflow detection is given in Table 3. The complexity of a conventional 16-bit overflow detector function is not extraordinary and the truth table may be satisfied with a straightforward logic design.
FIG. 1 illustrates a conventional overflow detection circuit for a 16-bit shifter. The circuit consists of three parts: a mask decoder generator at levels 101, 102, and 103; masking levels 104 and 105; and a propagation stage in levels 106 through 108. Shift value 100 is the number of bit positions the data is to be shifted during the impending shift in binary. The mask decoder generator at levels 101, 102 and 103 decodes the value into a series of binary digits called the shift mask S. When the shift value S is N, the shift mask consists of N bits of xe2x80x98lxe2x80x99s and M-N-1 bits of. xe2x80x980xe2x80x99s, where M is bit-length of the data. In the example illustrated above, with shift value binary xe2x80x980101xe2x80x99 (or decimal 5), the leading five bits D11 through D15 mark bit positions in which a xe2x80x981xe2x80x99 in the data produces an overflow. Mask generation is performed in logic levels 101 through 103. The 15-bit shift mask appears at the output of logic level 103. Recall that the least significant bit cannot generate an overflow. Then, a cluster of AND gates performs the masking operation driving outputs at level 104. The logic masks these bit positions in logic levels 101 through 103. Data information enters at level 104 and the resulting bit sequence from the masking operation enters at level 105. The remaining logic levels 106, 107, and 108 form an OR-tree to compute the presence of a data value of xe2x80x981xe2x80x99 within the masked field producing an overflow.
FIGS. 2A and 2B illustrate a conventional 32-bit overflow detector. FIG. 2A is the first portion and FIG. 2B the second portion of the logic. First note that several packets of signals form the interconnect between the two figures. Signal packet 201 passes the five shift bits S0 through 54 between the two drawings. Signal packet 202 passes several intermediate signals generated in FIG. 2B to inputs of logic in FIG. 2. Signal packet 203 passes the sixteen most significant data bits D31:D16 from FIG. 2A to FIG. 2B. Finally, two inputs 206 and 207 to OVF output gate 208 of FIG. 2A come from log-c generating these signals in FIG. 2B.
Table 4 shows the truth table for the 32-bit overflow detector function for shifters. This table can be applied directly to generation of the logic of FIGS. 2A and 2B which are most similar in organization to that of the conventional 16-Bit shifter overflow detector function of FIG. 1. It: is worthwhile to point out that in the design of many high speed logic functions optimal propagation delay performance dictates that each gate have a relatively small number of inputs. Often it is desirable to use cascaded two input gates in preference to less levels of gates having a large number of inputs (e.g. 8-input gates). Also it is sometimes preferable to use cascaded NAND gates to implement the logical equivalent of and AND-OR function for example. The cascaded NAND function appears in several parts of the logic of FIGS. 2A and 2B. One example is noted with NAND gates 211, 212, and 213 cascaded with NAND gate 205. Notice that in both the conventional 16-bit overflow function of FIG. 1 and the conventional 32-bit shifter of FIGS. 2A and 2B, decoding of the shift value precedes the input of data in the logic path. Levels 101, 102 perform the shift decoding in FIG. 1. Levels 201 and 202 perform shift value decoding in FIGS. 2A and 2B.
This invention describes a unique high-speed implementation for overflow detection logic to be used in high performance shifter functions. The overflow logic makes use of parallelism in combining shift value decoding and mask generation logic with the logic necessary to propagate data. Designs for both 16-bit and 32-bit shifters are presented and performance improvement of the new designs over conventional overflow detection circuits is demonstrated.